package com.xxwy.lintcode;

/**
 * @author xxwy
 * on 2018/10/8 0008
 * 题目：
 * Unique paths 计数
 * 有一个机器人的位于一个 m × n 个网格左上角。
 *
 * 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
 *
 * 问有多少条不同的路径？
 * -------------------
 * 例子:
 * 给出 m = 3 和 n = 3, 返回 6.
 * 给出 m = 4 和 n = 5, 返回 35.
 * |----------n（列）
 * |
 * |
 * m(行)
 */
public class Num114 {

    public int uniquePaths(int m, int n) {
        // write your code here
        int [][] f = new int[m][n];
        f[0][0] = 1;
        int i, j;
        //行
        for(i = 0;i< m;i++){
            //列
            for(j = 0;j< n;j++){
                if(j == 0 || i == 0){
                    f[i][j] = 1;
                }else {
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[m-1][n-1];
    }
}
